package com.ycz.algorithm.utils.queue;


/**
 * @author yancz
 * @ClassName LinkedListDeque
 * @description: 双向队列的双链表实现
 * @date 2024-11-28 15:39:37
 * @version: 1.0
 */
public class LinkedListDeque {

    private ListNode front; // 头结点

    private ListNode rear; // 尾结点

    private int dequeSize; // 队列长度

    // 初始化队列
    public LinkedListDeque() {
        front = null;
        rear = null;
    }

    // 获取队列长度
    public int size() {
        return dequeSize;
    }

    // 判断队空
    public boolean isEmpty() {
        return size() == 0;
    }

    /*
     * @author yancz
     * @description //TODO
     * @date 2024/11/28 15:57
     * @param num 入队元素值
     * @param isFront 是否队首入队，true表示队首入队，false表示队尾入队
     **/
    public void push(int num, boolean isFront) {
        ListNode node = new ListNode(num);
        if (isEmpty()) { // 队空
            front = rear = node;
        } else if (isFront) { // 如果是队首入队
            node.next = front; // 修改后继指向
            front.pre = node; // 修改前驱指向
            front = node; // 队首更新
        } else { // 队尾入队
            node.pre = rear; // 修改前驱指向
            rear.next = node; // 修改后继指向
            rear = node; // 队尾更新
        }
        dequeSize++; // 队列长度+1
    }

    // 队首入队
    public void pushFirst(int num) {
        push(num, true);
    }

    // 队尾入队
    public void pushLast(int num) {
        push(num, false);
    }

    /*
     * @author yancz
     * @description //TODO
     * @date 2024/11/28 16:26
     * @param isFront true表示队首出队，false表示队尾出队
     * @return int 返回出队元素值
     **/
    public int pop(boolean isFront) {
        if (isEmpty()) {
            throw new IndexOutOfBoundsException("队空！");
        }
        int val; // 用于暂存出队元素值
        if (isFront) { // 队首出队
            val = front.val;
            ListNode fNext = front.next; // 头结点的后继结点
            if (fNext != null) {
                fNext.pre = null;
                front.next = null;
            }
            front = fNext; // 更新头结点
        } else { // 队尾出队
            val = rear.val;
            ListNode rPre = rear.pre; // 尾结点的前驱结点
            if (rPre != null) {
                rPre.next = null;
                rear.pre = null;
            }
            rear = rPre; // 更新尾结点
        }
        dequeSize--; // 队列长度-1
        return val;
    }

    // 队首出队
    public int popFirst() {
        return pop(true);
    }

    // 队尾出队
    public int popLast() {
        return pop(false);
    }

    // 访问队首元素
    public int peekFirst() {
        if (isEmpty()) {
            throw new IndexOutOfBoundsException("队空！");
        }
        return front.val;
    }

    // 访问队尾元素
    public int peekLast() {
        if (isEmpty()) {
            throw new IndexOutOfBoundsException("队空！");
        }
        return rear.val;
    }

    // 转为数组
    public int[] toArray() {
        ListNode node = front;
        int[] res = new int[size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = node.val;
            node = node.next;
        }
        return res;
    }

    public static void main(String[] args) {
        LinkedListDeque linkedListDeque = new LinkedListDeque();
        // 队尾入队
        linkedListDeque.pushLast(1);
        linkedListDeque.pushLast(2);
        linkedListDeque.pushLast(3);
        // 队首入队
        linkedListDeque.pushFirst(4);
        linkedListDeque.pushFirst(5);
        commonPrint(linkedListDeque);
        // 队首出队
        System.out.println("出队元素：" + linkedListDeque.popFirst());
        commonPrint(linkedListDeque);
        // 队尾出队
        System.out.println("出队元素：" + linkedListDeque.popLast());
        commonPrint(linkedListDeque);
    }

    private static void commonPrint(LinkedListDeque linkedListDeque) {
        int[] arrs = linkedListDeque.toArray();
        for (int i : arrs) {
            System.out.print(i + "\t");
        }
        System.out.println();
        System.out.println("队列长度：" + arrs.length);
        System.out.println("队首元素：" + linkedListDeque.peekFirst());
        System.out.println("队尾元素：" + linkedListDeque.peekLast());
    }

}
